/**
 * 
 */
package arbreAbstrait;

/**
 *	<b>Classe Arbre</b>
 */
public class ArbreAVL {
	
	private static final int NULL = 0;
	private int taille;
	private int hauteur=0;
	private ElementAVL tab[];
	private ElementAVL tabTampon[];

	/**
	 * <b>Constructeur : Arbre</b></br>
	 * 
	 * <p>Créer une instance d'Arbre d'une hauteur passée en parramètre. 
	 * Les valeurs de chaque noeuds seront initialisées �  -1.</p>
	 * @param tailleArbre la taille du tableau
	 */
	public ArbreAVL(int tailleArbre) 
	{
		this.taille = tailleArbre;
		this.tab = new ElementAVL[this.taille];
		this.tabTampon = new ElementAVL[this.taille];
		for(int i=0; i<this.taille; ++i)
		{
			this.setNoeud(-1,i);
			this.tabTampon[i]= new ElementAVL(-1,i);
		}
		
	}
	
	public ElementAVL getElement(int indice)
	{
		if(this.getTaille()>indice)
		{
			return tab[indice];
		}
		else 
		{
			return new ElementAVL(-1);
		}
	}
	
	public int getTaille() {
		return taille;
	}

	public void setTaille(int taille) {
		this.taille = taille;
	}
	
	public void setNoeud(int valeur, int indice)
	{
		if (indice < this.getTaille())
		{
			this.tab[indice]=new ElementAVL(valeur,indice);
		}
	}
	
	public boolean desequilibre(int indice)
	{
		if((this.getElement(indice*2+1).getValeur()==-1)&&(this.getElement(indice*2).getValeur()==-1))
		{
			return true;
		}
		if((this.getElement(indice*2+1).getValeur()==-1)||(this.getElement(indice*2).getValeur()==-1))
		{
			return false;
		}
		if((desequilibre(2*indice+1))&&(desequilibre(2*indice)))
		{
			return true;
		}
		return false;
	}
	
	public boolean afilsGauche(int indice)
	{
		if((this.getElement(indice*2).getValeur()==-1))
		{
			return false;
		}
		return true;
	}
	public boolean afilsDroit(int indice)
	{
		if((this.getElement(indice*2+1).getValeur()==-1))
		{
			return false;
		}
		return true;
	}
	
	public int desequilibre2(int indice)
	{
		if(!this.afilsGauche(indice)&&this.afilsDroit(indice))
		{
			return -1;
		}
		if(this.afilsGauche(indice)&&!this.afilsDroit(indice))
		{
			return 1;
		}
		if(!(this.afilsGauche(indice)&&this.afilsDroit(indice)))
		{
			return this.getElement(indice).getHauteur();
		}
		return desequilibre2(2*indice)-desequilibre2(2*indice+1);
	}
	
	public void rotationDroiteGauche(int indice)
	{
		this.rotationDroite(indice*2+1);
		this.rotationGauche(indice);
	}
	
	public void rotationGaucheDroite(int indice)
	{
		this.rotationGauche(indice*2);
		this.rotationDroite(indice);
	}
	
	private void effacer (int i)
	{
		this.tabTampon[i]=new ElementAVL(-1);
		if(this.getTaille()>2*i)
		{
			if(tabTampon[2*i].getValeur()!=-1)
			{
				this.effacer(2*i);
			}
			if(tabTampon[2*i+1].getValeur()!=-1)
			{
				this.effacer(2*i+1);
			}
		}
	}
	
	public void rotationDroite(int i)
	{
		this.tabTampon=this.tab.clone();
	
		this.effacer(i);
		
		if(this.tab[2*i].getValeur()!=-1)
		{
			this.tabTampon[i]=this.tab[i*2];
			this.tabTampon[i*2+1]=this.tab[i];
			
			this.copier(4*i,2*i);
			this.copier(4*i+1,4*i+2);
			this.copier(2*i+1,4*i+3);
		}
		
		this.tab=tabTampon.clone();
	}
	
	public void rotationGauche(int i)
	{
		
		this.tabTampon=this.tab.clone();
		
		this.effacer(i);
		
		if(this.tab[2*i].getValeur()!=-1)
		{
			this.tabTampon[i*2]=this.tab[i];
			this.tabTampon[i]=this.tab[i*2+1];
			
			this.copier(2*i,4*i);
			this.copier(4*i+2,4*i+1);
			this.copier(4*i+3,2*i+1);
		}
		
		this.tab=tabTampon.clone();
	}
	
	private void copier(int i, int j)
	{
		//System.out.println("Copie. i : "+i+" j : "+j);
		//this.afficheArbre(1, 0);
		if(this.getTaille()>2*i)
		{
			this.tabTampon[j]=this.tab[i];
			if(this.tab[2*i].getValeur()!=-1)
			{
				this.copier(i*2,j*2);
			}
			if(this.tab[(2*i)+1].getValeur()!=-1)
			{
				this.copier((i*2)+1,(j*2)+1);
			}
		}
	}
	
	
	

	/**
	 * <b>Méthode : afficheArbre</b></br>
	 * Affiche l'arbre en console.
	 * 
	 * @param index L'indice du noeud �  afficher, 1 pour la racine
	 * @param espace Le nombre d'espace �  afficher avant l'arbre
	 */
	public void afficheArbre(int index, int espace) 
	{
		if(this.tab != null)
		{
			if(2*index+1<this.getTaille()) 
			{
				this.afficheArbre(2*index+1, espace+2);
			}
			
			for(int i=0; i<espace; ++i)
			{
				System.out.print("      ");
			}
			
			if(this.tab[index].getValeur()!=-1)
			{
				System.out.print(this.tab[index].getValeur()+"\n");
			}
			else
			{
				System.out.print("\n");
			}
			
			if(2*index<this.getTaille())
			{
				espace = espace+2;
				this.afficheArbre(2*index, espace);
			}
		}
	}

	
	/**
	 * <b>Méthode : afficheArbre</b></br>
	 * Affiche l'arbre en console.
	 * 
	 * @param index L'indice du noeud �  afficher, 1 pour la racine
	 * @param espace Le nombre d'espace �  afficher avant l'arbre
	 */
	public void afficheArbreRang(int index, int espace) 
	{
		if(this.tab != null)
		{
			if(2*index+1<this.getTaille()) 
			{
				this.afficheArbreRang(2*index+1, espace+2);
			}
			
			for(int i=0; i<espace; ++i)
			{
				System.out.print("      ");
			}
			
			if(this.tab[index].getValeur()!=-1)
			{
				//System.out.print(this.tab[index].getValeur()+"/"+this.getElement(index).getHauteur()+"\n");
				System.out.print(this.tab[index].getValeur()+"/"+this.getTaille(index,0)+"\n");
				//System.out.print(this.tab[index].getValeur()+"/"+this.getHauteurMax(index)+"\n");
			}
			else
			{
				System.out.print("\n");
			}
			
			if(2*index<this.getTaille())
			{
				espace = espace+2;
				this.afficheArbreRang(2*index, espace);
			}
		}
	}
	
	public int getTaille(int indice, int taille)
	{
		if(!this.afilsGauche(indice)&&this.afilsDroit(indice))
		{
			return getTaille(2*indice+1,++taille);
		}
		if(this.afilsGauche(indice)&&!this.afilsDroit(indice))
		{
			return getTaille(2*indice,++taille);
		}
		if(!(this.afilsGauche(indice)&&this.afilsDroit(indice)))
		{
			return ++taille;
		}
		return getTaille(2*indice,taille)+getTaille(2*indice+1,taille)+1;
	}	
	
	public void inserNoeud(ElementAVL el)
	{
		
	}
	
	public int getHauteurMax(int indice)
	{
		if(!this.afilsGauche(indice)&&this.afilsDroit(indice))
		{
			return getHauteurMax(2*indice+1);
		}
		if(this.afilsGauche(indice)&&!this.afilsDroit(indice))
		{
			return getHauteurMax(2*indice);
		}
		if(!(this.afilsGauche(indice)&&this.afilsDroit(indice)))
		{
			return this.getElement(indice).getHauteur();
		}
		return Math.max(getHauteurMax(2*indice),getHauteurMax(2*indice+1));
	}
	
	public void ajouter(ElementAVL el)
	{
		int x = this.ajout(el,1);
		this.reequilibrer((x-1)/2);
	}
	
	public int ajout(ElementAVL el, int indice)
	{
		/*
		if((!this.afilsGauche(indice)||!this.afilsDroit(indice))&& el.getValeur()<this.getElement(indice).getValeur())
		{
			this.setNoeud(el.getValeur(), indice*2);
		}
		if((!this.afilsGauche(indice)||!this.afilsDroit(indice))&& el.getValeur()>this.getElement(indice).getValeur())
		{
			this.setNoeud(el.getValeur(), indice*2+1);
		}
		else
		{
			if(el.getValeur()<=this.getElement(indice).getValeur())
			{
				ajout(el,indice*2);
			}
			else
			{
				ajout(el,indice*2+1);
			}
		}
		*/
		if(el.getValeur()<this.getElement(indice).getValeur())
		{
			if(!this.afilsGauche(indice))
			{
				this.setNoeud(el.getValeur(), indice*2);
				return indice;
			}
			else
			{
				return ajout(el,indice*2);
			}
		}
		else
		{
			if(!this.afilsDroit(indice))
			{
				this.setNoeud(el.getValeur(), indice*2+1);
				return indice;
			}
			else
			{
				return ajout(el,indice*2+1);
			}
		}
		//return indice;
	}
	
	public void reequilibrer(int indice)
	{
		if(this.getHauteurMax(indice*2)>this.getHauteurMax(indice*2+1)+1)
		{
			if(this.getHauteurMax(indice*4)>this.getHauteurMax((indice*2)*2+1))
			{
				this.rotationDroite(indice);
			}
			else
			{
				this.rotationGaucheDroite(indice);
			}
		}
		else
		{
			if(this.getHauteurMax(indice*2+1)>this.getHauteurMax(indice*2)+1)
			{

				if(this.getHauteurMax((indice*2+1)*2+1)>this.getHauteurMax((indice*2+1)*2))
				{
					this.rotationGauche(indice);
				}
				else
				{
					this.rotationDroiteGauche(indice);
				}
			}
		}
		
		//if(this.afilsDroit(indice))reequilibrer(indice*2+1);
		//if(this.afilsGauche(indice))reequilibrer(indice*2);
		
		
		/*
		if(this.getHauteurMax(indice*2)>=this.getHauteurMax(indice*2+1))
		{
			if(this.getHauteurMax(indice*4)<this.getHauteurMax((indice*2)*2+1))
			{
				this.rotationDroite(indice);
			}
			else
			{
				this.rotationGaucheDroite(indice);
			}
		}
		else
		{
			if(this.getHauteurMax(indice*2+1)>=this.getHauteurMax(indice*2))
			{

				if(this.getHauteurMax((indice*2+1)*2+1)<this.getHauteurMax((indice*2+1)*2))
				{
					this.rotationGauche(indice);
				}
				else
				{
					this.rotationDroiteGauche(indice);
				}
			}
		}
		*/
		
	}
	/*
	 * méthode de test*
	 */
	public void afficheHauteurs() 
	{
		System.out.println("Affichage des hateurs :");
		for(int i=0;i<this.getTaille();++i)
		{
			System.out.println("Hauteur de "+i+" : "+tab[i].getHauteur());
		}
		System.out.println("fin");
	}
	
	public int hauteurArbre()
	{
		return taille;
	}

	public int getHauteur() {
		return this.getHauteurMax(1);
	}


}
